1) Field of the Invention
The field of this invention is data integrity, and in particular generating and verifying a digital signature for a message or data file.
2) Background Art
When a message is transmitted from one party to another, the receiving party may desire to determine whether the message has been altered in transit. Furthermore, the receiving party may wish to be certain of the origin of the message. It is known in the prior art to provide both of these functions using digital signature algorithms. Several known digital signature algorithms are available for verifying the integrity of a message. These known digital signature algorithms may also be used to prove to a third party that the message was signed by the actual originator.
The use of public key cryptography to achieve instantiations of these digital signature algorithms is also known in the art. For example, Diffie and Hellman teach using public key cryptography to derive a digital signature algorithm in "New Directions in Cryptography," IEEE Transactions on Information Theory, Vol. IT-22 pp. 472-492, 1976. See also U.S. Pat. No. 4,200,770. Since then, several attempts have been made to find practical public key signature techniques which depend on the difficulty of solving certain mathematical problems to make message alteration or forgery by unauthorized parties difficult. For example, the Rivest-Shamir-Adleman system depends on the difficulty of factoring large integers. See R. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public Key Cryptosystems," Communications of the ACM, Feb. 1978, Vol. 21, No. 2, pp. 120-126, and U.S. Pat. No. 4,405,829.
Taher ElGamal teaches a signature scheme in "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms" in IEEE Transactions on Information Theory, Vol. IT-31, No. Jul. 4, 1985. It is believed that this system relies on the difficulty of computing discrete logarithms over finite fields. In the system taught by ElGamal m denotes a document to be signed, where 0.ltoreq.m.ltoreq.p-2 where p is a large prime and .alpha. is a primitive element mod p, both known. In any of the cryptographic systems based on discrete logarithms, p must be chosen such that p-1 has at least one large prime factor. If p-1 has only small prime factors, then computing the discrete logarithms is easy. The public file consists of a public key y.ident..alpha..sup.x mod p for each user where each user has a secret x, a large prime p, and a primitive element .alpha.. To sign a document, user A uses a secret key x.sub.A to find a signature for m in such a way that all users can verify the authenticity of the signature by using the public key y.sub.A together with .alpha. and p, and no one can forge a signature without knowing the secret X.sub.A.
The signature for m is the pair (r,s), 0.ltoreq.r,s&lt;p-1, chosen such that EQU .alpha..sup.m .ident.y.sup.r r.sup.s mod p Equation (1)
is satisfied.
In many applications it is convenient or necessary to sign the message on-line. However, the Rivest-Shamir-Adleman system is expensive to sign on-line. The system of ElGamal, however, allows much of the computation to be done prior to going on-line since use is made of values which are not dependent upon message m. Thus, on-line signature generation is very simple in the system of ElGamal.
The signing procedure in the method taught by ElGamal includes three steps. In the first step, a random number k is chosen such that k is uniformly between 0 and p-1, and gcd(k,p-1)=1. Next, r is determined by the relationship EQU r.ident..alpha..sup.k mod p. Equation (2)
In view of Equation (2), the relationship which must be satisfied for determining the signature for message m, as set forth in Equation (1), may be written as EQU .alpha..sup.m .ident..alpha..sup.xr .alpha..sup.ks mod p. Equation (3)
Equation (3) may be solved for s by using EQU m.ident.xr+ks mod (p-1). Equation (4)
Equation (4) has a solution for s provided k is chosen such that gcd(k, p-1)=1.
In the method taught by ElGamal it is easy to verify the authenticity of the signature (r,s) by computing both sides of Equation (1) and determining that they are equal. The chosen value of k should never be used more than once. This can be guaranteed, for example, by using a Data Encryption Standard chip in the counter mode as a stream cipher to generate values of k.
It is possible to attempt two types of attacks on the signature scheme of ElGamal. The first type of attack includes attacks designed to recover the secret key x. The second type of attack includes attacks designed to forge signatures without recovering x. Some of these attempted attacks are easily shown to be equivalent to computing discrete logarithms over GF(p).
In the first type of attack attempt an intruder may try to solve t equations of the form of Equation (4) when given {m.sub.i : i=1, 2, . . . , t} documents, together with the corresponding signatures {(r.sub.i,s.sub.i): i=1, 2, . . ., t}. However, there are t+1 unknowns in this system of equations since each signature uses a different value of k. Thus, this system of equations is underdetermined and the number of solutions is large. The reason is that each value of x yields a solution for the k.sub.i since a system of linear equations with a diagonal matrix of coefficients results. Since p-1 is chosen to have at least one large prime factor q, potential recovery of x mod q would require an exponential number of message-signature pairs. If any value of k is used twice in the signing, then the system of equations is uniquely determined and x may be recoverable. Thus, for the system of ElGamal to be secure, no value of k should be used more than once, as previously described.
In another attack attempt of this first type an intruder may try to solve equations of the form of Equation (3). This is always equivalent to computing discrete logarithms over GF(p), since both unknowns x and k appear in the exponent. In still another attack of this type an intruder may attempt to develop some linear dependencies among the unknowns {k.sub.i 1, 2, . . ., t}. This is also equivalent to computing discrete logarithms since if k.sub.i .ident.ck.sub.j mod (p-1), then r.sub.i .ident.r.sub.j.sup.c mod p, and if c can be computed then computing discrete logarithms is easy.
In the second type of attack attempt, trying to forge signatures without knowledge of x, a forger may try to find r and s such that Equation (1) is satisfied for a document m. If r.ident..alpha..sup.j mod p is fixed for some j chosen at random, then computing s is equivalent to solving a discrete logarithm problem over GF(p).
If the forger fixes s first, then r may be computed as follows: EQU r.sup.s y.sup.r .ident.A mod p. Equation (b)
Solving Equation (5) for r may not be as hard as computing discrete logarithms. However, it is believed that solving Equation (5) in polynomial time is not feasible. In another possible attack of the second type, a forger may try to solve Equation (1) for both r and s simultaneously. However, it is believed that an efficient algorithm for doing so is not known.
The signature scheme of ElGamal also permits an attack attempt wherein the intruder, knowing one legitimate signature (r,s) for one message m, may generate other legitimate signatures (r,s) and messages m. However, this attack attempt, although implementable, does not allow the intruder to sign an arbitrary message m and therefore does not break the system. This limited ability to create acceptable message-signature pairs can be avoided by requiring m to have a certain structure. Alternatively this can be avoided by applying a one-way function H to message m before signing it. This causes a potential forger to be unable to determine a value of m which corresponds to the H(m) which was signed using the method shown below. The forger must be able to transmit such an m to the verifier, if the forgery is to be considered successful.
Given a signature (r,s) for the legitimately signed message m, then EQU .alpha..sup.m .ident.y.sup.r r.sup.s mod p.
Integers A, B, and C are selected by the forger arbitrarily such that (Ar-Cs) is relatively prime to p-1. The values of r', s', m' are selected such that EQU r'=r.sup.A .alpha..sup.B y.sup.C mod p, EQU s'=sr'/(Ar-Cs) mod (p-1), EQU m'=r'(Am+Bs)/(Ar-Cs)mod (p-1).
Then it is claimed that (r',s') signs the message m': The verification equation will be satisfied, since ##EQU1## wherein all calculations are performed mod p.
As a special case, setting A=0, verifiable signatures (r',s') may be generated with corresponding messages m' , without access to any signature: EQU r'=.alpha..sup.B y.sup.C mod p, EQU s'=-r'/C mod (p-1), EQU m'=-r'B/C mod (p-1).
Thus it will be understood by those skilled in the art that applying a one-way function H to message m, prior to signing, thwarts the general and special-case attack attempts. It will also be understood that function H may be used to form a digest of long messages so that the signature function does not have to be iteratively applied to segments of the full message m. This results in further efficiency.
U.S. Pat. No. 4,995,082, issued to Schnorr, on Feb. 19, 1991, entitled "Method for Identifying Subscribers and for Generating and Verifying Electronic Signatures in a Data Exchange System," provides a system wherein communication and verification is more efficient relative to ElGamal. Additionally, the system of Schnorr maintains the extremely efficient on-line signing capability. However, some of the desirable features of ElGamal, as well as the extensive body of experience and literature associated with the ElGamal model, are not applicable to the Schnorr model.
Thus, it is desirable to provide a system having efficiencies of on-line signing, communication, and verification which are comparable to the system of Schnorr while still maintaining compatibility with the ElGamal model and its analytical tools. In particular, it is desirable to retain the complexity of the ElGamal signature equation which enables secure use of the straightforward expression H(m), rather than simplifying the signature equation at the expense of replacing H(m) by Schnorr's H(.alpha..sup.k mod p,m).